元胞自动机(CA)是自动机理论研究的离散计算模型。细胞自动机在许多领域都有应用,包括物理学、理论生物学和微观结构建模。

元胞自动机由一个规则的单元格网格组成,每个单元格处于有限数量的状态之一,例如开和关。网格可以有任意数量的维度。对于每个单元格,相对于指定的单元格定义了一组称为其邻域的单元格。通过为每个单元格分配一个状态来选择初始状态(时间t = 0)。根据某些固定的规则(通常是数学函数)创建新一代(将t前进1),该规则根据单元的当前状态及其邻近单元的状态确定每个单元的新状态。通常情况下,更新单元格状态的规则对每个单元格是相同的,不会随着时间的推移而改变,并同时应用于整个网格。 20世纪40年代,斯坦尼斯劳·乌兰和约翰·冯·诺伊曼在洛斯阿拉莫斯国家实验室(Los Alamos National Laboratory)发现了这个概念。虽然在20世纪50年代和60年代,一些人一直在研究这个问题,但直到20世纪70年代,康威的二维细胞自动机《生命的游戏》问世,人们对这个课题的兴趣才扩展到学术界之外。20世纪80年代,斯蒂芬·沃尔夫拉姆(Stephen Wolfram)从事了一维细胞自动机的系统研究,他称之为基本细胞自动机;他的研究助理马修·库克证明了其中一条规则是图灵完备的。

细胞自动机的主要分类,编号为1到4。它们依次是:模式通常稳定为同质的自动机,模式演变为基本稳定或振荡结构的自动机,模式以一种看似混乱的方式演变的自动机,以及模式变得极其复杂并可能持续很长时间的自动机,具有稳定的局部结构。

最后一类被认为在计算上是通用的,或者说能够模拟图灵机。

简介

模拟二维元胞自动机的一种方法是设想一张大的网格以及一组让细胞遵循的规则。每个方块被称为“细胞”,每个细胞有两种可能的状态,黑和白。细胞的邻域是相邻的细胞。两种最常见的社区类型是由四个正交相邻的细胞组成邻域以及四个对角相邻的单元。对于这样一个单元格及其邻域,有512(= $2^9$)种可能的模式。对于512种可能的模式中的每一种,规则表将说明在下一个时间间隔中中心单元格是黑还是白。康威的生命游戏是这个模型的一个流行版本。另一种常见的邻域类型是扩展的von Neumann邻域,它包括每个正交方向上最近的两个单元,共8个。这种规则系统的一般方程是$k^{k^s}$,其中k是一个单元格可能状态的数量,s是用于确定该单元格下一个状态的相邻单元格(包括要计算的单元格本身)的数量因此,在具有摩尔邻域的二维系统中,可能的自动机总数将是$2^{2^9}$,或1.34×$10^{154}$。

通常认为,每个细胞开始时的状态都是相同的,只有少数细胞处于其他状态;状态值的分配称为配置更普遍的说法是,有时假设一开始就有一个周期性的模式,只有有限数量的细胞违反了这个模式。后一种假设在一维元胞自动机中很常见。

历史

20世纪40年代,Stanislaw Ulam在洛斯阿拉莫斯国家实验室工作时,用一个简单的晶格网络作为模型,研究了晶体的生长与此同时,乌拉姆在洛斯阿拉莫斯的同事约翰·冯·诺伊曼(John von Neumann)正在研究自我复制系统的问题冯·诺伊曼最初的设计是基于一个机器人制造另一个机器人的概念。这种设计被称为运动学模型。在开发这个设计时,冯·诺伊曼开始意识到制造一个自我复制机器人的巨大困难,以及为机器人提供“大量零件”来制造它的复制体的巨大成本。诺伊曼在1948年的Hixon研讨会上写了一篇题为“自动机的一般和逻辑理论”的论文乌拉姆是建议使用离散系统来创建自我复制的简化模型的人。Nils Aall Barricelli对这些人造生命模型进行了许多最早的探索。

乌拉姆和冯·诺伊曼在20世纪50年代末发明了一种计算液体运动的方法。该方法的驱动概念是将液体视为一组离散单元,并根据其相邻单元的行为计算每个单元的运动第一个细胞自动机系统就这样诞生了。和乌拉姆的晶格网络一样,冯·诺伊曼的细胞自动机也是二维的,通过算法实现了自我复制。结果是一个通用的复制器和构造器在一个具有小邻域的细胞自动机中工作(只有那些接触的细胞是邻域;对于von Neumann的细胞自动机,只有正交细胞),并且每个细胞有29个状态。冯·诺伊曼通过设计一个20万个细胞结构来证明一种特定的模式可以在给定的细胞宇宙中无限复制自己。这种设计被称为镶嵌模型,被称为冯·诺依曼通用构造器。

同样在20世纪40年代,诺伯特·维纳(Norbert Wiener)和阿图罗·罗森布鲁斯(Arturo Rosenblueth)开发了一种具有细胞自动机某些特征的可兴奋介质模型他们的具体动机是对心脏系统脉冲传导的数学描述。但是他们的模型不是元胞自动机,因为信号传播的介质是连续的,波前是曲线。1978年,J. M. Greenberg和S. P. Hastings建立并研究了可激发介质的真元胞自动机模型;参见格林伯格-黑斯廷斯元胞自动机。Wiener和Rosenblueth的原始工作包含了许多见解,并继续被引用在关于心律失常和兴奋系统的现代研究出版物中

在20世纪60年代,细胞自动机作为一种特殊的动力系统被研究,并首次与符号动力学的数学领域建立了联系。1969年,Gustav a. Hedlund根据这一观点编制了许多结果,这篇论文至今仍被认为是细胞自动机数学研究的开创性论文。最基本的结果是在curtis - hedlundd - lyndon定理中将元胞自动机的全局规则集刻画为移位空间的连续自同构集。

1969年,德国计算机先驱康拉德·祖泽(Konrad Zuse)出版了《计算空间》一书,提出宇宙的物理定律本质上是离散的,整个宇宙是单个元胞自动机上确定性计算的输出;“祖斯的理论”成为数字物理学研究领域的基础

同样是在1969年,计算机科学家Alvy Ray Smith完成了斯坦福大学的一篇关于细胞自动机理论的博士论文,这是第一次将CA作为计算机的一般类别进行数学处理。许多论文都来自这篇论文:他证明了各种形状的邻域的等价性,如何化简摩尔邻域为冯·诺依曼邻域,或如何化简任何邻域为冯·诺依曼邻域。他证明了二维CA是计算通用的,引入了一维CA,并表明它们也是计算通用的,即使具有简单的邻域他展示了如何将复杂的von Neumann证明的构造普适性(以及自复制机器)纳入到一维CA计算普适性的结果中。作为von Neumann关于CA的书的德语版的介绍,他写了一份该领域的调查,参考了几十篇论文,来自许多国家的许多作者在十年左右的工作中,经常被现代CA研究人员忽视

20世纪70年代,一种名为Game of Life的双状态二维细胞自动机广为人知,尤其是在早期的计算社区中。由约翰·康威发明,马丁·加德纳在《科学美国人》的一篇文章中推广,规则如下:

分类

Wolfram在《一种新型科学》和20世纪80年代中期的几篇论文中,根据细胞自动机和其他一些简单的计算模型的行为,定义了四种类型。细胞自动机的早期研究倾向于识别特定规则的模式类型,Wolfram的分类是对规则本身进行分类的第一次尝试。按复杂性排序,这些类是:

第2类稳定或振荡结构可能是最终结果,但达到这种状态所需的步骤可能非常多,即使初始模式相对简单。最初模式的局部变化可能会无限扩散。Wolfram推测,许多4类细胞自动机(如果不是全部的话)都能够进行通用计算。

受Wolfram分类法的启发,已经有人尝试将细胞自动机按照严格的形式分类。例如,Culik和Yu提出了三个定义良好的类(以及第四个不匹配这些自动机的类),它们有时被称为Culik-Yu类;这些组织的成员资格被证明是无法确定的。Wolfram的第2类可以被分成两组,分别是稳定的(定点的)和振荡的(周期性的)规则

有4类动力系统的想法最初来自诺贝尔奖获得者化学家伊利亚·普里戈因,他确定了这4类热力系统(1)热力学平衡系统,(2)空间/时间均匀系统,(3)混沌系统,(4)复杂的远离平衡的耗散结构系统(见Nicolis论文中的图1(普里戈因的学生))

关联的自动机

元胞自动机的概念有许多可能的推广。

一种方法是使用矩形(立方等)以外的网格。例如,如果一个平面用正六边形平铺,这些六边形可以用作单元格。在许多情况下,得到的元胞自动机等价于具有特殊设计的邻域和规则的矩形网格。另一种变体是使网格本身不规则。

此外,规则可以是概率的,而不是确定性的。这种元胞自动机称为概率元胞自动机。一个概率规则给出了,对于t时刻的每种模式,中心细胞在t + 1时刻转变到每种可能状态的概率。有时使用更简单的规则;例如:“规则就是生命游戏,但在每个时间步中,每个细胞转变成相反颜色的概率为0.001%。”

邻里关系或规则会随着时间或空间的变化而变化。例如,最初一个细胞的新状态可以由水平相邻的细胞决定,但对于下一代来说,将使用垂直的细胞。

在细胞自动机中,一个细胞的新状态不受其他细胞的新状态影响。这可以改变,例如,一个2 × 2的单元格块可以由它自己和相邻的单元格确定。

有连续的自动机。它们类似于整体细胞自动机,但不是规则和状态是离散的(例如,一个表,使用状态{0,1,2}),而是使用连续函数,状态变为连续的(通常值为[0,1])。位置的状态是有限数量的实数。某些细胞自动机可以以这种方式产生液体模式的扩散。

连续空间自动机具有连续的位置。位置的状态是有限数量的实数。时间也是连续的,状态根据微分方程演化。一个重要的例子是反应-扩散纹理,这是艾伦·图灵提出的微分方程,用来解释化学反应如何产生斑马身上的条纹和豹子身上的斑点当这些被元胞自动机近似时,它们通常会产生相似的模式。MacLennan将连续空间自动机作为计算模型。

有一些已知的连续空间自动机的例子,它们展示了类似于生命游戏中的滑翔机的传播现象

基本元胞自动机

最简单的非平凡细胞自动机是一维的,每个细胞有两种可能的状态,细胞的邻居定义为相邻细胞的两侧。一个单元格和它的两个相邻单元格组成一个由3个单元格组成的邻域,因此邻域有$2^3 = 8$种可能的模式。规则由决定每个模式的单元格在下一代中是1还是0组成。那么就有$2^8 = 256$个可能的规则.

这256个元胞自动机通常引用Wolfram代码,Wolfram代码是Wolfram发明的一种标准命名约定,为每个规则提供从0到255的数字。许多论文对这256个元胞自动机进行了分析和比较。规则30、规则90、规则110和规则184细胞自动机特别有趣。下面的图像显示了规则30和110的历史,当初始配置由1(在每个图像的顶部)和0包围时。每一行像素代表自动机历史上的一代,t=0是最上面一行。每个像素用白色表示0,黑色表示1。

规则空间

一基本等元胞自动机规则由8位指定,所有基本元胞自动机规则都可以被认为位于8维单位超立方体的顶点上。这个单位超立方就是元胞自动机规则空间。对于次近邻元胞自动机,规则由$2^5 = 32$位指定,元胞自动机规则空间为32维单位超立方体。两个规则之间的距离可以通过从一个顶点(代表第一个规则)到另一个顶点(代表另一个规则)沿着超立方体的边缘移动所需的步数来定义。这种规则与规则之间的距离也被称为汉明距离。

元胞自动机规则空间允许我们问这样一个问题:具有相似动力学行为的规则是否彼此“接近”。在二维平面上图形化地绘制高维超立方体仍然是一项艰巨的任务,超立方体中规则的一个粗略定位器是基本规则的8位字符串(或下最近邻规则的32位字符串)中位-1的数量。在规则空间的这些片中绘制不同Wolfram类中的规则,表明第1类规则倾向于具有较少的位-1数量,因此位于空间的一个区域,而第3类规则倾向于具有较高的位-1比例(50%)

对于较大的元胞自动机规则空间,表明第4类规则位于第1类和第3类规则之间。这一观察结果是混沌边缘这一短语的基础,并使人联想到热力学中的相变。

参考资料: